Tên gọi Ô Cầu Dền Theo cố giáo sư Trần Quốc Vượng cho hay: trước đó, cái tên này đã xuất hiện ở cố đô Hoa Lư (Trường Yên, Ninh Bình) với tấm bia cổ, chiếc cầu đá bắc qua sông Hoàng Long và cũng là một cửa ngõ của kinh thành Hoa Lư. Vì lẽ đó, có tác giả đã cho rằng cái tên Ô Cầu Dền cũng như nhiều tên khác ở Hà Nội: Cầu Đông, Chợ Dừa, Đình Ngang... đã được Lý Thái Tổ mang từ cố đô Hoa Lư ra kinh đô mới Thăng Long cách đây nghìn năm trước.

Theo một tích khác cửa ô Cầu Dền lại chép: đời nhà Mạc, ở làng Kim Liên có một người học trò cha mẹ chết sớm, nhà nghèo, phải đi dạy học kiếm ăn qua ngày. Mấy năm đói kém, nhờ có mấy mẫu ruộng rau dền nên anh đã cứu giúp được nhiều người qua khỏi nạn đói. Vì thế, người ta gọi chỗ ở của anh là Cầu Dền. Các cụ cao niên ở đây vẫn còn nhớ vùng này xưa kia (và thậm chí cho đến những năm 1945 - 1954) có con sông nhỏ dẫn nước thải từ nội thành ra, hai bên bờ có đất bãi phù sa, rau màu quanh năm xanh tốt. Trong đó có rau dền là nhiều hơn cả. Chiếc cầu bắc qua con sông hai bên bờ có nhiều rau dền nên gọi là Cầu Dền.